#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/12 11:26
# @Author  : Yuyun
# @File    : 监控二叉树.py
# @IDE     : PyCharm

class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    """
    局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
    整体最优：全部摄像头数量所用最少！
    """
    def monitor_tree(self, root:TreeNode):
        """
        result = [0]
        st = []
        if root:
            st.append(root)
        node = root
        while st:
            node = st.pop()
            if node != None:

                # node.right == None and node.left == None；node无覆盖
                #
                # node.right == None and node.left.val == 0：node装摄像头
                # node.right == None and node.left.val == 1：node有覆盖
                # node.right == None and node.left.val == 2：node无覆盖
                #
                # node.right.val == 0 and node.left == None：node装摄像头
                # node.right.val == 1 and node.left == None：node有覆盖
                # node.right.val == 2 and node.left == None：node无覆盖
                #
                # node.right.val == 0 and node.left.val == 0：node装摄像头
                # node.right.val == 1 and node.left.val == 1：node有覆盖
                # node.right.val == 2 and node.left.val == 2：node无覆盖

                if (node.right == None and node.left == None) or (node.right.val == 2 and node.left == None)\
                        or (node.right.val == 2 and node.left == None) or (node.right.val == 2 and node.left.val == 2):
                    node.val = 0
                elif (node.right == None and node.left.val == 0) or (node.right.val == 0 and node.right.val == 0)\
                            or (node.right.val == 0 and node.left == None):
                    node.val = 1
                    result[0] += 1
                elif (node.right == None and node.left.val == 1) or (node.right.val == 1 and node.left == None)\
                        or (node.right.val == 1 and node.left.val == 1):
                    node.val = 2
                st.append(node)  # 中
                st.append(None)
                if node.right:  # 右
                    st.append(node.right)
                if node.left:  # 左
                    st.append(node.left)
            else:
                node = st.pop()
        if node.val == 0:
            result[0] += 1
        return result
        """
        res = [0]
        #   此处使用列表，函数使用引用传递；
        #   还可以直接将res 初始化为Solution的类属性，使用__init__()初始化，traversal（root）仅传递节点值，不再传递res
        if self.traversal(root, res) == 0:
            res[0] += 1
        return res[0]
    def buildtree_levelord(self, nums):
        if not nums:
            return
        root = TreeNode(nums[0])
        queue = [root]
        i = 1
        while queue and i < len(nums):
            node = queue.pop()
            if nums[i] != None:
                node.left = TreeNode(nums[i])
                queue.append(node.left)
            i += 1
            if i < len(nums) and nums[i] != None:
                node.right = TreeNode(nums[i])
                queue.append(node.right)
            i += 1
        return root

    def traversal(self, root:TreeNode, res):
        """
        # 0: 该节点未覆盖
        # 1: 该节点有摄像头
        # 2: 该节点有覆盖，None节点也表示有覆盖
        """
        if not root:
            return 2
        left = self.traversal(root.left, res)
        right = self.traversal(root.right, res)

        if left == 2 and right == 2:
            return 0
        if left ==0 or right == 0:
            res[0] += 1
            return 1

        if left == 1 or right == 1:
            return 2

if __name__ == '__main__':
    nums = eval(input())
    solution = Solution()
    binary_tree = solution.buildtree_levelord(nums)
    result = solution.monitor_tree(binary_tree)
    print(result)
